Compilers are generally used to transform one representation of a computer program procedure into another representation. Typically, but not exclusively, compilers are used to transform a human readable form of a program such as source code into a machine readable form such as object code.
One type of compiler is an optimizing compiler which includes an optimizer or optimizing module for enhancing the performance of the machine readable representation of a program. Some optimizing compilers are separate from a primary compiler, while others are built into a primary compiler to form a multi-pass compiler. Both types of compilers may operate either on a human readable form, a machine readable form, or any intermediate representation between these forms.
Many optimizing modules of compilers operate on intermediate representations of computer programs or procedures. Typically a program or procedure being translated is broken down into a series of "statements", each of which contains zero or more "operands" or "data items". A data item may be "defined", meaning that it is given a value by the statement, or "used", meaning that its value is fed into the computation represented by the statement. For example, the statement "x=y+z" defines x and uses y and z.
During optimization, possible paths of execution through a procedure may be represented by a control flow graph (CFG). Statements may be grouped together into basic blocks, which are maximal sequences of straight-line code. In other words, there is no way to branch into or out of a basic block except at the beginning or end. A CFG is a graph with one node for each basic block in the procedure. The CFG includes an arc from block A to block B if it is possible for block B to be executed immediately after block A has been executed.
A definition of a data item is said to "reach" a use of that data item if there is a path in the CFG from the definition to the use, along which the data item is not redefined. In this case the use is called a "reachable use" for the definition.
One optimization that is typically performed in many compilers is copy propagation, which attempts to remove unnecessary copy statements (e.g., of the form "T=S", where T is a target, or defined operand, and S is a source, or used operand) from a program. Such copy statements may be introduced by the programmer; however, they may also be generated by the compiler, e.g., when the compiler breaks down complex source code into its basic components, and during many optimization phases.
Conventional copy propagation techniques operate by looking for copy statements of the form "T=S" and examining each of the copy's reachable uses of the copy target T. A reachable use U is said to be "eligible" for propagation from such a copy C, provided that: (1) every path from the beginning of the program to U passes through C; (2) along every path from C to U, neither S nor T is redefined; and (3) replacing the use of T in U by a use of S would not violate any machine-specific idiomatic rules.
If all of C's reachable uses are eligible for propagation according to this definition, all reachable uses of T may be replaced with uses of S, and the copy statement "T=S" can be eliminated. This process of replacing the reachable uses and eliminating the copy is referred to as "propagating" the copy.
While this form of copy propagation has been found to be beneficial in enhancing the performance of computer programs, it has been found that conventional techniques are often too restrictive, and often miss potential optimizations. For example, conventional copy propagation does not allow a copy statement "T=S" to be removed when any of the reachable uses of "T" is ineligible for propagation. This is true even if only one of many uses of "T" is ineligible.
This limitation in traditional copy propagation is a substantial blockade to program optimization in some environments; therefore, a substantial need has arisen for copy propagation which goes beyond conventional copy propagation techniques to further optimize a computer program and thus improve the resulting performance of the program.